<?php
/**
 * @author : lihui
 * @email  : lihui@mama.com
 * @time   : 2022/11/10 17:27
 * 最大堆：
 * 1. 任意一个结点都大于等于它的孩子结点
 * 2. 用数组实现，左结点就是2*i+1，右结点就是2*i+2，父结点就是(i-1)/2
 */

namespace Xxb\XxbPhpAlgo;

class MaxHeap extends FixedArray
{
    /**
     * 指定位置的左结点索引
     * @param $index
     *
     * @return mixed
     */
    public function leftChildIndex($index)
    {
        return 2 * $index + 1;
    }

    /**
     * 指定位置的右结点索引
     * @param $index
     *
     * @return mixed
     */
    public function rightChildIndex($index)
    {
        return 2 * $index + 2;
    }

    /**
     * 指定位置的父结点
     * @param $index
     *
     * @return mixed
     */
    public function parentIndex($index)
    {
        if ($index <= 0) {
            throw new \InvalidArgumentException('index must be gt 0');
        }

        return intdiv($index - 1, 2);
    }

    /**
     * 往堆的最后加入新元素
     * @param $ele
     */
    public function push($ele)
    {
        $this->addLast($ele);
        $this->shiftUp($this->size - 1);
    }

    /**
     * 结点上浮：
     * 从指定结点开始，把比父结点大的子结点移动到父结点位置
     * 如果出现数据交换，要继续向上比较，以维护任意结点都大于等于它的子结点规则
     * @param $index
     */
    private function shiftUp($index)
    {
        while ($index > 0 && $this->get($index) > $this->get($this->parentIndex($index))) {
            // 用更大的子结点替换父结点
            $temp = $this->get($this->parentIndex($index));
            $this->set($this->parentIndex($index), $this->get($index));
            $this->set($index, $temp);
            $index = $this->parentIndex($index);
        }
    }

    /**
     * 取出堆的最大元素：
     * 1. 第一个元素就是最大的，返回即可
     * 2. 把最后一个元素放到第一个位置
     * 3. 进行下浮操作：
     * 从第一个位置开始向下比较，把最大值替换上来，最小值推下去
     * 如果发生了数据交换，则从交换位置继续重复下浮操作
     * @return mixed
     */
    public function extractMax()
    {
        $result = $this->getFirst();
        $this->set(0, $this->getLast());
        $this->removeLast();
        $this->shiftDown(0);
        return $result;
    }

    /**
     * 结点下沉：
     * 1. 判断当前结点和它的左右子结点谁更大
     * 2. 把大的值放到当前位置，且需要继续向下维护任意结点要大于等于它的子结点的规则
     * 3. 如果没有比当前位置更大的子结点，则结束下沉操作
     * @param $index
     */
    private function shiftDown($index)
    {
        /**
         * 假设可以一直下沉，则最多下沉到某个叶子结点
         * 由于叶子结点没有子结点了 不需要继续下沉操作
         * 如果用index < 数组最大索引做循环条件也是可以的
         * 只是这变成了另外的语义 即任意的即将下沉的结点位置都在数组最大索引范围内
         */
        while ($this->leftChildIndex($index) < $this->size) {
            // 比较index结点和它的左右子结点
            $maxIndex = $index; // 假设最大值的索引就是当前位置
            if (isset($this->data[$this->leftChildIndex($index)])
                && $this->data[$index] < $this->data[$this->leftChildIndex($index)]) {
                // index结点比左结点小
                $maxIndex = $this->leftChildIndex($index);
            }

            if (isset($this->data[$this->rightChildIndex($index)])
                && $this->data[$maxIndex] < $this->data[$this->rightChildIndex($index)]) {
                // 右结点最大
                $maxIndex = $this->rightChildIndex($index);
            }

            if ($maxIndex == $index) {
                // index结点最大，结束下沉操作
                break;
            }

            // 把最大值放到index位置
            $temp = $this->data[$index];
            $this->data[$index] = $this->data[$maxIndex];
            $this->data[$maxIndex] = $temp;

            // 继续维护新结点所在的树的大小
            $index = $maxIndex;
        }
    }

    /**
     * 获取堆中的最大值
     * @return mixed
     */
    public function getMax()
    {
        return $this->getFirst();
    }

    /**
     * 替换最大值结点
     * @param $ele
     *
     * @return mixed
     */
    public function replaceMax($ele)
    {
        $max = $this->getMax();
        $this->set(0, $ele);
        $this->shiftDown(0);
        return $max;
    }

    /**
     * 数组堆化
     * @param $array
     */
    public function heapify($array)
    {
        if (!is_array($array)) {
            throw new \InvalidArgumentException('param must be array');
        }

        if (empty($array)) {
            throw new \RuntimeException('array is empty');
        }

        $this->size = count($array);
        if (!($array instanceof \SplFixedArray)) {
            $temp = new \SplFixedArray($this->size);
            for ($i=0; $i<$this->size; $i++) {
                $temp[$i] = $array[$i];
            }
            $this->data = $temp;
        }

        $startIndex = $this->parentIndex($this->size - 1);
        for ($i=$startIndex; $i>=0; $i--) {
            $this->shiftDown($i);
        }
    }
}
